#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

//杨氏矩阵
//时间复杂度（最坏的情况下的一个数量级）小于o(N):N个元素遍历的话，时间复杂度等于O（N）；
//杨氏矩阵下最右上角的元素，为一行中的最大元素，一列中的最小元素，
//所以拿一个元素和最右上角的元素比较，可以去掉一行或者是一列
//一直比较到左下角，仍然没有找到，溢出；没有找到
//可以从右上角比较，也可以从左下角比较

//从右上角开始找起
void find_k(int arr[][3], int l, int c, int k)
{
	int x = 0;
	int y = c - 1;
	int flag = 0;
	while (x <= l - 1 && y >= 0)
	{
		if (arr[x][y] < k)
		{
			x++;
		}
		else if (arr[x][y] > k)
		{
			y--;
		}
		else
		{
			printf("找到了，元素的下标为 %d %d", x, y);
			flag = 1;
			break;
		}
	}
	if (flag == 0)
	{
		printf("该元素不存在");
	}
}
int main()
{
	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
	int k = 10;//k为我们要找的元素
	find_k(arr, 3, 3, k);
	return 0;
}

//从左下角元素开始找起
//void find_k(int arr[][3], int l, int c, int k)
//{
//	int x = l-1;
//	int y = 0;
//	int flag = 0;
//	while (x>=0 && y<=c-1)
//	{
//		if (arr[x][y] < k)
//		{
//			y++;
//		}
//		else if (arr[x][y] > k)
//		{
//			x--;
//		}
//		else
//		{
//			printf("找到了，元素的下标为 %d %d", x, y);
//			flag = 1;
//			break;
//		}
//	}
//	if (flag == 0)
//	{
//		printf("该元素不存在");
//	}
//}
//int main()
//{
//	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
//	int k = 6;//k为我们要找的元素
//	find_k(arr, 3, 3, k);
//	return 0;
//}